package problem10_Regular_Expression_Matching;

public class Solution2 {
	public boolean isMatch(String s, String p) {
		if(p.length()<=1) {
			if(p.equals(".")){
				if(s.length()==1)
					return true;
			}
			return s.equals(p);
		}
		if(p.charAt(1)!='*'){
			char toBeChecked=s.length()>0?s.charAt(0):'\0';
			return (p.charAt(0)==toBeChecked||p.charAt(0)=='.'&&Character.isLetter(toBeChecked))&&isMatch(s.length()>1?s.substring(1):"",p.substring(1));
		}else{
			int index=0;
			while(index<s.length()&&s.charAt(index)==p.charAt(0)||p.charAt(0)=='.'&&index<s.length()){
				if(isMatch(s.length()>index+1?s.substring(index+1):"",p.length()>2?p.substring(2):"")) return true;
				index++;
			}
		}
		return isMatch(s,p.length()>2?p.substring(2):"");
	}
	
	public static void main(String[] args){
		System.out.println(new Solution2().isMatch("a", ".*..a"));
	}
}
